【Ant Trip】题解

2024-07-16 12:07| 来源: 网络整理| 查看: 265

题目描述

给你无向图的n个点和m条边，保证这m条边都不同且不会存在同一点的自环边，现在问你至少要几笔才能所有边都画一遍。（一笔画的时候笔不离开纸）

输入格式多组数据，每组数据用空行隔开。对于每组数据，第一行两个整数n, m表示点数和边数。接下去m行每行两个整数a, b，表示a, b之间有一条边。

输出格式对于每组数据，输出答案。

样例输入 3 3 1 2 2 3 1 3 4 2 1 2 3 4

样例输出

1 2

分析

做这道题，首先我们需要知道这些：

若一张图只有一个点，那么一笔都不需要画假如他是一个半欧拉图，那么也只需要一笔以上两种都不是的话，那么我们需要画的笔数应该等于这张图中度为奇数的点数之和除以 2

那么我们怎么判断是否为一个欧拉图呢？暴搜？记得雷老师说过，假如一张图是欧拉图，那么他的所有点的度应该都是偶数。其实这道题的题目并没有说所给出的数据是一张连通图，所以我们又可以用一个并查集来求出每一个联通分量，并用一个数组来存储这个联通分量之中的度为奇数的点的个数（好像有点啰嗦）

看懂了的话，可以自己实现一遍，发现有问题再看代码吧~

代码 #include #include #include #include #include using namespace std; const int MAXN = 1e5 * 2 + 5; int fa[MAXN]; int in[MAXN]; int num[MAXN]; int ans[MAXN]; int Find (int x) { if (fa[x] != x) fa[x] = Find (fa[x]); return fa[x]; }//找爸爸 int main() { int n, m; while ((scanf("%d %d", &n, &m)) != EOF) { for (int i = 1; i

【本文地址】

公司简介

联系我们